/**
 * 除自身以外数组的乘积
 * 给定一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积
 * 要求：时间复杂度 O(n)，空间复杂度 O(1)（输出数组不计入空间复杂度）
 * 
 * 算法思路：使用前缀乘积和后缀乘积
 * 1. 第一次遍历：计算每个位置左侧所有元素的乘积（前缀乘积）
 * 2. 第二次遍历：计算每个位置右侧所有元素的乘积（后缀乘积），并与前缀乘积相乘
 */
function productExceptSelf(nums: number[]): number[] {
    // 初始化结果数组，所有元素初始值为 1
    const result = new Array(nums.length).fill(1);
    
    // 第一次遍历：计算前缀乘积
    // prefix 表示当前位置左侧所有元素的乘积
    let prefix = 1;
    for (let i = 0; i < nums.length; i++) {
        // 将当前位置的前缀乘积存入结果数组
        result[i] *= prefix;
        // 更新前缀乘积，为下一个位置做准备
        prefix *= nums[i];
    }
    
    // 第二次遍历：计算后缀乘积并乘到结果中
    // postfix 表示当前位置右侧所有元素的乘积
    let postfix = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        // 将当前位置的后缀乘积乘到结果数组中
        result[i] *= postfix;
        // 更新后缀乘积，为前一个位置做准备
        postfix *= nums[i];
    }
    
    return result;
}
